//
//  main.c
//  AlgorithmLearning
//
//  Created by aron on 2017/11/1.
//  Copyright © 2017年 aron. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "QuickSort.h"
#include "InsertionSort.h"
#include "HeapStruct.h"
#include "HeapSort.h"
#include "BubbleSort.h"
#include "ShellSort.h"
#include "MergeSort.h"
#include "PrintUtil.h"
#include "Tree.h"

void testQuickSort();
void testInsertionSort();
void testHeapSort();
void testBubbleSort();
void testShellSort();
void testMergeSort();
void testTree();

int main(int argc, const char * argv[]) {
    
    // 快排
//    testQuickSort();
    
    // 插入排序
//    testInsertionSort();
    
    // 冒泡排序
//    testBubbleSort();
    
    // 堆排序
//    testHeapSort();
    
    // Shell排序
//    testShellSort();
    
    // 归并排序
//    testMergeSort();
    
    // 二叉树
    testTree();
    
    return 0;
}

void testQuickSort() {
    unsigned int seed = (unsigned int)time(NULL);
    srand(seed);
    
    int count = 20;
    ElementType arr[count];
    for (int i = 0; i < count; i++) {
        arr[i] = rand() % count;
    }
    
    printf("原始数据：\n");
    printArr(arr, count, ascRule);
    printf("\n");
    
    // 快速排序
    _Bool useQuickSort = 1;
    if (useQuickSort) {
        Quicksort(arr, count);
        printf("排序数据：\n");
        printArr(arr, count, ascRule);
        printf("\n");
    }
}

void testInsertionSort() {
    unsigned int seed = (unsigned int)time(NULL);
    srand(seed);
    
    int count = 20;
    ElementType arr[count];
    for (int i = 0; i < count; i++) {
        arr[i] = rand() % count;
    }
    
    printf("原始数据：\n");
    printArr(arr, count, ascRule);
    printf("\n");
    
    _Bool useInsertionSort = 1;
    if (useInsertionSort) {
        Insertionsort1(arr, count);
        printf("排序数据：\n");
        printArr(arr, count, ascRule);
        printf("\n");
    }
}

void testHeapSort() {
    unsigned int seed = (unsigned int)time(NULL);
    srand(seed);
    
    int count = 22;
    PriorityQueue H = PQ_Initialize(count);
    for (int i = 0; i < count; i++) {
//        PQ_InsertToMinQueue(rand() % count, H);
        PQ_InsertToMaxQueue(rand() % count, H);
    }
    printPQStructure(H);
    
    // 保存的数组
    ElementType arr[count];
    
    printf("排序数据：\n");
    int j;
    int countxx = H->Size;
    // for (j = 0; j<H->Size; j++) !! 不能这么写，H->Size会变化，最终只执行 H->Size/2 次循环
    for (j = 0; j<countxx; j++) {
        ElementType min = PQ_DeleteMax(H);
        // printf("%d ", min);
        arr[j] = min;
    }
    printArr(arr, count, descRule);
}

void testBubbleSort() {
    unsigned int seed = (unsigned int)time(NULL);
    srand(seed);
    
    int count = 100;
    ElementType arr[count];
    for (int i = 0; i < count; i++) {
        arr[i] = rand() % count;
    }
    
    printf("原始数据：\n");
    printArr(arr, count, ascRule);
    printf("\n");
    
    Bubblesort(arr, count);
    printf("排序数据：\n");
    printArr(arr, count, ascRule);
    printf("\n");
}

void testShellSort() {
    unsigned int seed = (unsigned int)time(NULL);
    srand(seed);
    
    int count = 100;
    ElementType arr[count];
    for (int i = 0; i < count; i++) {
        arr[i] = rand() % count;
    }
    
    printf("原始数据：\n");
    printArr(arr, count, ascRule);
    printf("\n");
    
    Shellsort(arr, count);
    printf("排序数据：\n");
    printArr(arr, count, ascRule);
    printf("\n");
}

void testMergeSort() {
    unsigned int seed = (unsigned int)time(NULL);
    srand(seed);
    
    int count = 100;
    ElementType arr[count];
    for (int i = 0; i < count; i++) {
        arr[i] = rand() % count;
    }
    
    printf("原始数据：\n");
    printArr(arr, count, ascRule);
    printf("\n");
    
    MergeSort(arr, count);
    printf("排序数据：\n");
    printArr(arr, count, ascRule);
    printf("\n");

}

void testTree() {
    unsigned int seed = (unsigned int)time(NULL);
    srand(seed);
    
    int count = 100;
    ElementType arr[count];
    for (int i = 0; i < count; i++) {
        arr[i] = rand() % count;
    }
    
    printf("原始数据：\n");
    printArr(arr, count, ascRule);
    printf("\n");

    SearchTree Tree = NULL;
    for (int i = 0; i < count; i++) {
        ElementType Elem = arr[i];
        Tree = Tree_Insert(Elem, Tree);
    }
    
    // 查找最小
    Position minPos = Tree_FindMin(Tree);
    printf("min: %d\n", minPos->Element);
    
    // 查找最大
    Position maxPos = Tree_FindMax(Tree);
    printf("max: %d\n", maxPos->Element);
    
    // 删除节点
    Tree_Delete2(minPos->Element, Tree);
    Tree_Delete2(maxPos->Element, Tree);
    
    printf("\n");
    printf("排序数据：\n");
    // 遍历二叉树
    Tree_LMR_Travel(Tree);
    printf("\n");
}

